\chapter{Monoidální reprezentace}


Zatímco v minulé kapitole jsme popsali vztah regularity bezkontextovych přepisovacích systémů pomocí nevyhnutelnosti, v této kapitole si ukážeme více algebraický pokus o charakterizaci přepisovacích systémů generující regulární jazyky. Tento popis bude korespondovat s dobře známým vztahem regulárních jazyků s kongruencemi konečných indexů. První výsledek této kapitoly je svým způsobem přirozené rozšíření této charakterizace na přepisovací systémy.

\begin{definice}
Nechť $\leq$ je předuspořádání na množině $\Sigma^*$, $w \in\Sigma^* $ a $L \subset \Sigma^*$. Potom 
\[cl_{\leq}(w)=\{x\in \Sigma^* | w\leq x\}\]
\[cl_{\leq}(L)=\bigcup_{w \in L}cl_{\leq}(w)\]
Potom relace $\leq$ je regulátor, pokud platí $[cl_{\leq}(L)$ je regulární pro každý $L$ regulární, a úplný regulátor, pokud  $[cl_{\leq}(L)$ je regulární pro libovolný jazyk $L$.
\end{definice}

\begin{veta}
\label{monoid}
Nechť $(\Sigma, R)$ je bezkontextový přepisovací systém a $\Rightarrow_R^*$ je jeho relace odvození. Potom $\Rightarrow_R^*$ je regulátor, právě když existuje konečný monoid $M$, homomorfismus monoidů $h:\Sigma^* \rightarrow M$ a předuspořádání $\leq$ na $M$ tak, že pro každé $a \in \Sigma$ a $x \in \Sigma^*$ platí, že 
\[a \Rightarrow_R^* x \Longleftrightarrow h(x)\leq h(x).\]
\end{veta}

Důkaz předchozí věty lze najít v [2]. Na základě předchozí věty budeme definovat monoidální reprezentaci jazyka.

\begin{definice}
Nechť $(\Sigma, R)$ je bezkontextový přepisovací systém, $M$ monoid, $h:\Sigma^* \rightarrow M$ homomorfismus monoidů a $\leq$ monotónní předuspořádání na $M$. Trojice $(M, h, \leq)$  se nazývá monoidální reprezentace systému $(\Sigma, R)$, pokud pro každé $a \in \Sigma$ a $x \in \Sigma^*$ platí $a \Rightarrow^*_R x$, právě když $h(x)\leq h(x)$. $(M, h, \leq)$ je konečná monoidální reprezencate systému $(\Sigma, R)$, pokud $M$ je konečný monoid.
\end{definice}

Věta \ref{monoid} se dá použitím předchozí definice přeformulovat do následujícího tvaru.

\begin{veta}
Nechť $(\Sigma, R)$ je bezkontextový přepisovací systém. Potom $\Rightarrow_R^*$ je regulátor, právě když $(\Sigma, R)$ má konečnou reprezentaci.
\end{veta}

Je přirozené charakterizovat úplné regulátory definované bezkontextovými přepisovacími systémy. Podle věty \ref{genMyh} jsou to ty, jejihž relace odvození jsou dobrými předuspořádáními. Tato charakterizace je ovšem zatím pouze částečná. 

\begin{veta}
Nechť $(\Sigma, R)$ je bezkontextový přepisovací systém a $(G, h, \leq)$ je monoidální reprezentace, kde $G$ je konečná grupa. Potom $\Rightarrow_R^*$  je úplný regulátor na $\Sigma^*$.
\end{veta}

\cleardoublepage

